package com.hy.treeNode2;

import com.hy.treeNode.TreeNode;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class SymmetricTreeNode {


    /***
     * 101. 对称二叉树
     * 力扣题目链接
     *
     * 给定一个二叉树，检查它是否是镜像对称的。
     *
     * 例如： 层序遍历   二叉树 [1,2,2,34,4,3] 是对称
     *
     * 思路
     * 首先想清楚，判断对称二叉树要比较的是哪两个节点，要比较的可不是左右节点！
     *
     * 对于二叉树是否对称，要比较的是根节点的左子树与右子树是不是相互翻转的，理解这一点就知道了其实我们要比较的是两个树（这两个树是根节点的左右子树），所以在递归遍历的过程中，也是要同时遍历两棵树。
     *
     * 那么如果比较呢？
     *
     * 比较的是两个子树的里侧和外侧的元素是否相等。如图所示：
     *
     * 那么遍历的顺序应该是什么样的呢？
     *
     * 本题遍历只能是“后序遍历”，因为我们要通过递归函数的返回值来判断两个子树的内侧节点和外侧节点是否相等。
     *
     * 正是因为要遍历两棵树而且要比较内侧和外侧节点，所以准确的来说是一个树的遍历顺序是左右中，一个树的遍历顺序是右左中。
     *
     * 但都可以理解算是后序遍历，尽管已经不是严格上在一个树上进行遍历的后序遍历了。
     *
     * 其实后序也可以理解为是一种回溯，当然这是题外话，讲回溯的时候会重点讲的。
     *
     * 说到这大家可能感觉我有点啰嗦，哪有这么多道理，上来就干就完事了。别急，我说的这些在下面的代码讲解中都有身影。
     *
     * 那么我们先来看看递归法的代码应该怎么写。
     *
     * 递归法
     * 递归三部曲
     *
     * 1. 确定递归函数的参数和返回值
     * 因为我们要比较的是根节点的两个子树是否是相互翻转的，进而判断这个树是不是对称树，所以要比较的是两个树，参数自然也是左子树节点和右子树节点。
     *
     * 2. 确定终止条件
     * 要比较两个节点数值相不相同，首先要把两个节点为空的情况弄清楚！否则后面比较数值的时候就会操作空指针了。
     *
     * 节点为空的情况有：（注意我们比较的其实不是左孩子和右孩子，所以如下我称之为左节点右节点）
     *
     * 左节点为空，右节点不为空，不对称，return false
     * 左不为空，右为空，不对称 return false
     * 左右都为空，对称，返回true
     * 此时已经排除掉了节点为空的情况，那么剩下的就是左右节点不为空：
     *
     * 左右都不为空，比较节点数值，不相同就return false
     * 此时左右节点不为空，且数值也不相同的情况我们也处理了。
     *
     * 3. 确定单层递归的逻辑
     * 此时才进入单层递归的逻辑，单层递归的逻辑就是处理 左右节点都不为空，且数值相同的情况。
     *
     * 比较二叉树外侧是否对称：传入的是左节点的左孩子，右节点的右孩子。
     * 比较内测是否对称，传入左节点的右孩子，右节点的左孩子。
     * 如果左右都对称就返回true ，有一侧不对称就返回false 。
     * 代码如下：
     *
     * bool outside = compare(left->left, right->right);   // 左子树：左、 右子树：右
     * bool inside = compare(left->right, right->left);    // 左子树：右、 右子树：左
     * bool isSame = outside && inside;                    // 左子树：中、 右子树：中（逻辑处理）
     * return isSame;
     *
     * 如上代码中，我们可以看出使用的遍历方式，左子树左右中，右子树右左中，所以我把这个遍历顺序也称之为“后序遍历”（尽管不是严格的后序遍历）。
     */
     // 比较 左右子树  节点
    public boolean compare(TreeNode left,TreeNode right){
        if (left != null && right == null){
            return false;
        }
        if (left == null && right != null){
            return false;
        }
        if (left == null && right == null){
            return true;
        }
        // 节点  不为空  比较两节点的值
        if (left.val != right.val){
            return false;
        }

        // 比较  外侧
        boolean compare1 = compare(left.left, right.right);
        // 比较 内侧
        boolean compare2 = compare(left.right, right.left);

        return compare1 && compare2;
    }

    /**
     * 递归法
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root){
       return compare(root.left,root.right);
    }

    /**
     * 迭代法
     * 使用双端队列，相当于两个栈
     * @param root
     * @return
     */
    public boolean isSymmetric2(TreeNode root){
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offerLast(root.left);
        deque.offerFirst(root.right);

        while (!deque.isEmpty()){
            TreeNode leftNode = deque.pollFirst();
            TreeNode rightNode = deque.pollLast();

            if (leftNode == null && rightNode == null){
                continue;
            }
            if (leftNode != null && rightNode == null){
                return false;
            }
            if (leftNode == null && rightNode != null){
                return false;
            }
            if (leftNode.val != rightNode.val){
                return false;
            }
            // 外侧
            deque.offerFirst(leftNode.left);
            deque.offerLast(rightNode.right);
            // 内侧
            deque.offerFirst(leftNode.right);
            deque.offerLast(rightNode.left);
        }
        return true;
    }

    /**
     * 迭代法
     *  普通队列
     * @param root
     * @return
     */
    public boolean isSymmetric3(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root.left);
        queue.offer(root.right);

        while (!queue.isEmpty()){
            TreeNode leftNode = queue.poll();
            TreeNode rightNode = queue.poll();

            if (leftNode == null && rightNode == null){
                continue;
            }
            if (leftNode != null && rightNode == null){
                return false;
            }
            if (leftNode == null && rightNode != null){
                return false;
            }
            if (leftNode.val != rightNode.val){
                return false;
            }
            // 外侧
            queue.offer(leftNode.left);
            queue.offer(rightNode.right);
            // 内侧
            queue.offer(leftNode.right);
            queue.offer(rightNode.left);
        }
        return true;
    }
    public static void main(String[] args) {

        TreeNode leftNode3 = new TreeNode(8, null, null);
        TreeNode rightNode3 = new TreeNode(8, null, null);

        TreeNode leftNode2 = new TreeNode(4, null, null);
        TreeNode rightNode2 = new TreeNode(3, null, rightNode3);

        TreeNode leftNode1 = new TreeNode(3, leftNode3, null);
        TreeNode rightNode1 = new TreeNode(4, null, null);

        TreeNode leftNode = new TreeNode(2, leftNode1, rightNode1);
        TreeNode rightNode = new TreeNode(2, leftNode2, rightNode2);

        TreeNode root = new TreeNode(1, leftNode, rightNode);

        SymmetricTreeNode sym = new SymmetricTreeNode();

        System.out.println("是否是镜像对称(递归): "+sym.isSymmetric(root));
        System.out.println("是否是镜像对称(迭代-双向队列): "+sym.isSymmetric2(root));
        System.out.println("是否是镜像对称(迭代-普通队列): "+sym.isSymmetric3(root));
    }
}
